# 填充每个节点的下一个右侧节点指针

# Definition for a Node.
class Node(object):
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

# 层序遍历


class Solution(object):
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if not root:
            return
        layer = [root]
        while layer:
            length = len(layer)
            for i in range(length):
                if i == length - 1:
                    layer[i].next = None
                else:
                    layer[i].next = layer[i+1]
            for _ in range(length):
                node = layer.pop(0)
                if node.left:
                    layer.append(node.left)
                if node.right:
                    layer.append(node.right)
        return root


# 使用已经建立的next指针
class Solution(object):
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if not root:
            return
        root.next = None
        layer = [root]
        while layer:
            for i in range(len(layer)):
                if layer[i].left:
                    layer[i].left.next = layer[i].right
                if layer[i].right:
                    if i == len(layer) - 1:
                        layer[i].right.next = None
                    else:
                        layer[i].right.next = layer[i+1].left
            for _ in range(len(layer)):
                node = layer.pop(0)
                if node.left:
                    layer.append(node.left)
                if node.right:
                    layer.append(node.right)
        return root
